// 319. 灯泡开关 medium

// 初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。
// 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。
// 第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
//
// 示例:
//     输入: 3
// 输出: 1
// 解释:
//     初始时, 灯泡状态 [关闭, 关闭, 关闭].
//         第一轮后, 灯泡状态 [开启, 开启, 开启].
//         第二轮后, 灯泡状态 [开启, 关闭, 开启].
//         第三轮后, 灯泡状态 [开启, 关闭, 关闭].
//         你应该返回 1，因为只有一个灯泡还亮着。



/**
 * 超时
 * @param {number} n
 * @return {number}
 */
var bulbSwitch = function(n) {
    if(n === 1) return 1;
    if(n === 2) return 1;
    if(n === 3) return 1;
    let arr = [0]
    // 模拟灯泡数组
    for(let i = 1; i <= n; i++){
        arr.push(false);
    }
    // 模拟操作
    for(let i = 1; i <= n; i++){
        for(let j = 1; j <= n; j++){
            if (j % i === 0){
                arr[j] = !arr[j];
            }
        }
    }

    let count = 0;
    for(let i = 1; i <= n; i++){
        if(arr[i]) count++;
    }
    return count;
};



// 拿到题目首先想模拟n次开关过程，结果数据量太大超时了，27/35，n=99999.
// 于是转而观察某个位置，看看某个位置是怎样变化的，什么条件下会翻转
// 第18个灯泡会在1,2,3,6,9,18轮翻转。
// 第36个灯泡会在1,2,3,4,6,9,12,18,36轮翻转。
// 规律显而易见，只有在轮数是该位置因数的时候才会执行翻转操作。
//
// 于是我们回答了那个问题：只要找到该位置的所有因数个数，我们就知道该位置翻转了多少次。
// 更进一步的，除了完全平方数，因数都是成对出现的，这意味着实际起到翻转作用(0->1)的，只有
// 完全平方数而已。
// 此时任务已经大大简化，因为n个灯泡翻转n轮，我们只要看看到n位置，一共有多少个完全平方数即可。

var bulbSwitch2 = (n) => {
    return ~~Math.sqrt(3)
};

console.log(bulbSwitch2(4))